//
//  SortSolution.cpp
//  leetcode
//
//  Created by Ellie on 2021/2/7.
//  Copyright © 2021 Ellie. All rights reserved.
//

#include "SortSolution.hpp"
#include "Helper.h"

// 147. 对链表进行插入排序
// 稳定排序
ListNode* SortSolution::sortInsertion(ListNode* head)
{
    if(head == nullptr || head->next == nullptr)
        return head;
    ListNode dummyNode = ListNode(0);
    dummyNode.next = head;
    ListNode* start = head->next;
    ListNode* lastsorted = head;
    // lastsorted 永远指向已经排序的最后一个node
    // 已经排序的不做任何的插入操作，继续往后走
    while(start != nullptr)
    {
        if(lastsorted->val <= start->val)
        {
            lastsorted = lastsorted->next;
        }
        else
        {
            // find and insert
            ListNode* cur = start;
            lastsorted->next = start->next;
            ListNode* pre = &dummyNode;
            ListNode* node = pre->next;
            while(node != nullptr && node->val < cur->val)
            {
                pre = node;
                node = node->next;
            }
            pre->next = cur;
            cur->next = node;
        }
        start = lastsorted->next;
    }
    return dummyNode.next;
}

// find the left node[left, right)
// not same to https://leetcode-cn.com/problems/middle-of-the-linked-list/
/*
 
 ListNode* middleNode(ListNode* head) {
     if(head == nullptr)
        return head;
     ListNode* fast = head;
     ListNode* slow = head;
     
     while(fast != nullptr && fast->next != nullptr)
     {
        slow = slow->next;
        fast = fast->next->next;
     }
     return slow;
 }
 
 used for 输入一个数组，生成一个平衡二叉树
 
 */
ListNode* SortSolution::getMedian(ListNode* left, ListNode* right)
{
    if(left == nullptr)
        return nullptr;
    
    ListNode* slow = left;
    ListNode* fast = left->next;
    
    while(fast != right && fast->next != right)
    {
        fast = fast->next;
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

ListNode* SortSolution::sortMerge(ListNode* head)
{
    if(head == nullptr || head->next == nullptr)
        return head;
    ListNode* mid = this->getMedian(head, nullptr);
    ListNode* midnext = mid->next;
    mid->next =  nullptr;
    
    ListNode* left = sortMerge(head);
    ListNode* right = sortMerge(midnext);
    
    ListNode* ret = sortMerge(left, right);
    return ret;
}

// 递归合并两个有序链表，代码比较简单
// 排序算法中还是建议直接使用迭代的方法合并，减少空间复杂度，递归调用系统自动维护的堆栈
ListNode* SortSolution::sortMerge(ListNode* l1, ListNode* l2)
{
    if(l1 == nullptr) return l2;
    if(l2 == nullptr) return l1;
    
    ListNode* head = nullptr;
    if(l1->val <= l2->val)
    {
        head = l1;
        head->next = sortMerge(l1->next, l2);
    }
    else
    {
        head = l2;
        head->next = sortMerge(l1, l2->next);
    }
    return head;
}

vector<int> SortSolution::sortBubble(vector<int>& input)
{
    int size = input.size();
    for(int i=0; i < size - 1;i++)
    {
        for(int j = 0;j < size - i - 1;j++)
        {
            if(input[j] > input[j + 1])
            {
                swap(input[j], input[j + 1]);
            }
        }
    }
    return input;
}


// find the min element in unsorted list int every loop
// if not same just swap
vector<int> SortSolution::sortSelection(vector<int>& input)
{
    int size = input.size();
    for(int i=0;i<size;i++)
    {
        int index = i;
        for(int j=i + 1;j<size;j++)
        {
            if(input[j] < input[index])
            {
                index = j;
            }
        }
        if(index != i)
        {
            swap(input[index], input[i]);
        }
    }
    return input;
}

// [] -> [1] ->[1,2]
// 直接将大的元素往右边移动，而不是每次都交换元素
// 针对细节过一遍算法即可
vector<int> SortSolution::sortInsertion(vector<int>& input)
{
    int size = input.size();
    for(int i = 1; i < size;i++)
    {
        int temp = input[i];
        int j = i;
        for(; j >= 1 ;j--)
        {
            if(input[j - 1] > temp)
                input[j] = input[j - 1];
            else
                break;
        }
        input[j] = temp;
    }
    return input;
}

// 希尔排序是基于插入排序
// 插入排序每次都要将元素插入到合适的位置，涉及到元素的两两交换，不适合数量较大的排序
// 希尔排序，将排序进行分块处理，然后块插入到块，数组内任意间隔都是有序的，权衡了子数组的规模和有序性
// use gap to sort and redcue the gap
// 可以任意的选择gap，编写Shell排序可以先将插入排序写出来然后修改gap即可
// Using Marcin Ciura's gap sequence, with an inner insertion sort.
/*
 找到特定的gap
 # Sort an array a[0...n-1].
 gaps = [701, 301, 132, 57, 23, 10, 4, 1]
 
 # Start with the largest gap and work down to a gap of 1
 foreach (gap in gaps)
 {
     # Do a gapped insertion sort for this gap size.
     # The first gap elements a[0..gap-1] are already in gapped order
     # keep adding one more element until the entire array is gap sorted
     for (i = gap; i < n; i += 1)
     {
         # add a[i] to the elements that have been gap sorted
         # save a[i] in temp and make a hole at position i
         temp = a[i]
         # shift earlier gap-sorted elements up until the correct location for a[i] is found
         for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
         {
            a[j] = a[j - gap]
         }
         # put temp (the original a[i]) in its correct location
         a[j] = temp
     }
 }
 
 */
vector<int> SortSolution::sortShell(vector<int>& input)
{
    int size = input.size();
    int h = 1;
    while( h<size/3 )
        h = 3 * h + 1;
    
    while(h >= 1)
    {
        // 将数组变为h有序
        for(int i=h ; i<size; i++)
        {
            int temp = input[i];
            int j = i;
            for(; j >= h; j -= h)
            {
                if(input[j - h] > temp)
                    input[j] = input[j - h];
                else
                    break;
            }
            input[j] = temp;
        }
        h = h/3;
    }
    return input;
}

// 归并排序
// 分治divide and conquer
// bottom to top
void SortSolution::sortMerge(vector<int>& input)
{
    int size = input.size();
    sortMerge(input, 0, size - 1);
}

void SortSolution::sortMerge(vector<int>& input, int low, int high)
{
    if(low >= high)
        return;
    int mid = (high - low) / 2 + low;
    sortMerge(input, low, mid);
    sortMerge(input, mid + 1, high);
    // mergestable(input, low, mid, high);
    merge(input, low, mid, high);
}

// not-in place merge
void SortSolution::merge(vector<int>& input, int low, int mid, int high)
{
    // merge [low-mid] [mid+1-high]
    vector<int> temp;
    int left =  low;
    int right =  mid + 1;
    while(left <= mid && right <= high)
    {
        if(input[left] <= input[right])
        {
            temp.push_back(input[left]);
            left ++;
        }
        else{
            temp.push_back(input[right]);
            right ++;
        }
    }
    while (left <= mid) {
        temp.push_back(input[left++]);
    }
    while(right <= high)
    {
        temp.push_back(input[right++]);
    }
    // copy to input
    int index = 0;
    while(low <= high)
    {
        input[low++] = temp[index++];
    }
}

void SortSolution::mergestable(vector<int>& input, int low, int mid, int high)
{
    // tempv.size() == input.size()
    vector<int> tempv(input.size());
    for(int i=low;i<=high;i++)
    {
        tempv[i] = input[i];
    }
    
    int i = low;
    int j = mid + 1;
    for(int k=low;k<=high;k++)
    {
        // 左半边用尽适用右半边
        if(i > mid) input[k] = tempv[j++];
        // 右半边用尽用左半边
        else if(j > high) input[k] = tempv[i++];
        // left <= right 用左半边
        else if(tempv[i] <= tempv[j]) input[k] = tempv[i++];
        // left > right 用右半边
        else input[k] = tempv[j++];
    }
}

// 快速排序
// 分治divide and conquer
// top to bottom
// 递归定义
void SortSolution::sortQuick(vector<int>& input)
{
    int size = input.size();
    sortQuick(input, 0, size - 1);
}

void SortSolution::sortQuick(vector<int>& input, int low, int high)
{
    if(low >= high)
        return;
    int pivot = partition(input, low, high);
    sortQuick(input, low, pivot - 1);
    sortQuick(input, pivot + 1, high);
}

// 切分函数
// use double arrow left and right
// 双指针技巧
int SortSolution::partition(vector<int>& input, int low, int high)
{
    // 1. take pivot
    // 2. make partition
    // 3. return pivot index
    int pivot = input[low];
    int i = low;
    for(int j=low+1;j<=high;j++)
    {
        if(input[j] <= pivot)
        {
            i++;
            swap(input[i], input[j]);
        }
    }
    // i 一定是小于 pivot的值,如果小于交换位置
    swap(input[low], input[i]);
    return i;
}

int SortSolution::random_partition(vector<int>& input, int low, int high)
{
    // random partition
    // [low,high]
    int index = rand() % (high - low + 1) + low;
    swap(input[index], input[low]);
    return partition(input, low, high);
}

void SortSolution::sortwithpriority_queue(vector<int>& nums, bool ascendorder)
{
    if(!ascendorder)
    {
        // 降序排序，使用大顶堆
        priority_queue<int> que(nums.begin(), nums.end());
        nums.clear();
        while(!que.empty())
        {
            nums.push_back(que.top());
            que.pop();
        }
    }
    else
    {
        // 升序排序，使用小顶堆
        priority_queue<int, vector<int>, greater<int>> que(nums.begin(), nums.end());
        nums.clear();
        while(!que.empty())
        {
            nums.push_back(que.top());
            que.pop();
        }
    }
}

void SortSolution::sortHeap(vector<int>& nums, bool ascendorder)
{
    if(ascendorder)
    {
        myheap maxheap;
        maxheap.heapsortascend(nums);
    }
    else
    {
        myheap minheap;
        minheap.heapsortdescend(nums);
    }
}


int SortSolution::findKthLargest(vector<int> &nums, int k)
{
//    // NLogN mergesort-quicksort-headsort
//    // use std::sort and get the Kth largest num
//    int size = nums.size();
//    std::sort(nums.begin(), nums.end());
//    return nums[size - k];
    
//    // use priority_queue<int> less; 大顶堆
//    // 删除K - 1个元素，que当前的top就是第K大的元素
//    priority_queue<int> que(nums.begin(), nums.end());
//    int size = nums.size();
//    while(k-- > 1)
//    {
//        que.pop();
//    }
//    return que.top();
    int size = nums.size();
    myheap heap;
    heap.buildMaxHeap(nums, size);
    while(k -- > 1)
    {
        size --;
        swap(nums[0], nums[size]);
        heap.maxHeapify(nums, 0, size);
    }
    return nums[0];
}

// O(n)推导过程比较复杂，线性的选择方法，「《算法导论》9.2：期望为线性的选择算法
int SortSolution::findKthLargestPartition(vector<int>& nums, int low, int high, int k)
{
    int pivot = random_partition(nums, low, high);
    if(pivot == k)
        return nums[pivot];
    else if(pivot > k)
        return findKthLargestPartition(nums, low, pivot - 1, k);
    else
        return findKthLargestPartition(nums, pivot + 1, high, k);
}

// Top-K
vector<int> SortSolution::topKFrequent(vector<int>& nums, int k)
{
    vector<int> result;
    unordered_map<int, int> countmap;
    for(auto & v : nums)
    {
        countmap[v] ++;
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
    for(auto & v : countmap)
    {
        que.push({v.second, v.first});
        if(que.size() > k)
            que.pop();
    }
    while(!que.empty())
    {
        pair<int,int> cur = que.top();
        result.push_back(cur.second);
        que.pop();
    }
    return result;
}

// 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
double SortSolution::findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
    return 0.0;
}

vector<vector<int>> SortSolution::kClosest(vector<vector<int>>& points, int K)
{
    // 构建大顶堆，因为求解的是最近的问题
    vector<vector<int>> result;
    priority_queue<pair<int, int>> que;
    for(int i=0;i<K;i++)
    {
        que.push({pow(points[i][0],2) + pow(points[i][1], 2), i});
    }
    for(int i=K;i<points.size();i++)
    {
        int value = pow(points[i][0],2) + pow(points[i][1], 2);
        pair<int,int> cur = que.top();
        if(cur.first > value)
        {
            que.pop();
            que.push({value, i});
        }
    }
    while(!que.empty())
    {
        pair<int, int> cur = que.top();
        que.pop();
        result.push_back(points[cur.second]);
    }
    return result;
}

// Top K高频的单词，频率相同按照字符顺序排序
struct topkworldcompare
{
    bool operator()(const pair<int, string>& a, const pair<int, string>& b)
    {
        return a.first > b.first || (a.first == b.first && a.second < b.second);
    }
};

// 维护一个大小为K的小顶推
vector<string> SortSolution::topKFrequent(vector<string>& words, int k)
{
    vector<string> result;
    // 简化代码
    using pis = pair<int, string>;
    priority_queue<pis, vector<pis>, topkworldcompare> que;
    unordered_map<string, int> countmap;
    for(auto & value : words)
    {
        countmap[value] ++;
    }
    for(auto & value : countmap)
    {
        que.push({value.second, value.first});
        if(que.size() > k)
            que.pop();
    }
    while(!que.empty())
    {
        pis value = que.top();
        result.push_back(value.second);
        que.pop();
    }
    reverse(result.begin(), result.end());
    return result;
}

void myheap::heapsortascend(vector<int>& nums)
{
    int size = nums.size();
    buildMaxHeap(nums, size);
    while(size -- > 0)
    {
        swap(nums[0], nums[size]);
        maxHeapify(nums, 0, size);
    }
}

void myheap::heapsortdescend(vector<int>& nums)
{
    int size = nums.size();
    buildMinheap(nums, size);
    while(size -- > 0)
    {
        swap(nums[0], nums[size]);
        minHeapify(nums, 0, size);
    }
}

// Max-Heap
void myheap::buildMaxHeap(vector<int>& nums, int heapsize)
{
    int index = heapsize / 2;
    for(;index >= 0;index--)
    {
        maxHeapify(nums, index, heapsize);
    }
}

void myheap::maxHeapify(vector<int>& nums, int i, int heapsize)
{
    while(true)
    {
        int maxpos = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if(left < heapsize && nums[left] > nums[maxpos])
            maxpos = left;
        if(right < heapsize && nums[right] > nums[maxpos])
            maxpos = right;
        if(maxpos == i)
            break;
        swap(nums[maxpos], nums[i]);
        i = maxpos;
    }
}

// Min-Heap
void myheap::buildMinheap(vector<int>& nums, int heapsize)
{
    int index = heapsize / 2;
    for(;index >= 0; index--)
    {
        minHeapify(nums, index, heapsize);
    }
}

void myheap::minHeapify(vector<int>& nums, int i, int heapsize)
{
    while(true)
    {
        int minpos = i;
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        if(left < heapsize && nums[left] < nums[minpos])
            minpos = left;
        if(right < heapsize && nums[right] < nums[minpos])
            minpos = right;
        if(minpos == i)
            break;
        swap(nums[minpos], nums[i]);
        i = minpos;
    }
}
